googologywikiaorg-20200223-history
User blog:TheKing44/Grand Finale Functions
Rayo's function grows faster than any function definable in first-order set theory. However, it would be incorrect that this function settles Googology in first-order set theory, since it is not itself definable in that language. It would only be fair to compare it to other functions inexpressible in that language. Note that for the purposes of this article, we will be talking about first-order set theory whose semantics is given by \(V\) . Theories like MK are not considered part of first-order set theories in this sense, even though it uses the same symbols. In this post, I will define a family of extremely fast growing functions that can be defined in first-order set theory. First, some prerequisites. Satisfaction A satisfaction predicate tells you which arguments satisfy a formula. More formally, for a satisfaction predicate \(\#\) , we must have \(\forall x,y,\dots,z. \#('\phi', (x,y,\dots,z)) \iff \phi(x,y,\dots,z)\) for every formula \(\phi\) . For more information see this. We can not define a satisfaction predicate in first order set theory that works for every formula in first order set theory. We can however define a satisfaction predicate over a subset of such formulas. Bounded Quantifier Formulas We can define a \(\#_\text{Bounded}\) for formulas that only contain bounded quantifiers. Given a formula \(\phi\) with arguments \(x,y,\dots,z\) , we first pick some set that contains \(x,y,\dots,z\) and is transitive. This set will function as our universe. We will call it \(U\) . We will also require \(U\) to be contain each of its finite subsets. Then there will be a unique relation \(\#_U\) on variables assignments with range \(U\) and formulas such that :\(\#(x ``='' y, \overrightarrow v) \iff \overrightarrow v(x) = \overrightarrow v(y)\) :\(\#(x ``\in'' y, \overrightarrow v) \iff \overrightarrow v(x) \in \overrightarrow v(y)\) :\(\#(``\lnot \phi'', \overrightarrow v) \iff \lnot \#(``\phi'', \overrightarrow v)\) :\(\#(``\phi \lor \psi'', \overrightarrow v) \iff \#(``\phi'', \overrightarrow v) \lor \#(``\phi'', \overrightarrow v)\) :\(\#(``\phi \land \psi'', \overrightarrow v) \iff \#(``\phi'', \overrightarrow v) \land \#(``\phi'', \overrightarrow v)\) :\(\#(``\exists'' x ``\in'' y ``. \phi'', \overrightarrow v) \iff \exists z \in \overrightarrow v(y). \#(``\phi'', \overrightarrow v:= z)\) :\(\#(``\forall'' x ``\in'' y ``. \phi'', \overrightarrow v) \iff \forall z \in \overrightarrow v(y). \#(``\phi'', \overrightarrow v:= z)\) (where \(x\) and \(y\) represent variable symbols from whatever variable alphabet we are using). For convenience, we will extend the language with terms for finite sets. This will make working with tuples easier. This is why we required \(U\) to contain each of its subsets. We also modify \(\#_U\) to evaluate these terms as needed. So, \(\#_\text{Bounded}(\phi, (x, y, \dots, z))\) holds if and only if there exists a \(U\) and \(\#_U\) such that \((\phi, (x, y, \dots, z)) \in \#_U\) . Lévy hierarchy formulas The Lévy hierarchy is a way of categorizing formulas in the language of first-order set theory. Each (is equivalent to a formula that) has a fixed number of unbounded quantifiers. How do we define satisfaction predicates for these? Well, since the quantifiers are unbounded, there can not be a suitable relation \(\#_U\) since it will be the size of a proper class (which first-order set theory can not talk about). However, we can basically "hard code" the unbounded quantifiers in. For example, here is a satisfaction predicate for \(\Pi^{ZFC}_3\) : :\(\exists \psi. \psi \in \Sigma_3 \land ZFC \vdash \phi ``\iff'' \psi \land \forall q. \exists r. \forall s. \#_\text{Bounded}(\overline \psi, (q, r, s, x, y, \dots, z))\) where \(\overline \psi\) is \(\psi\) with the unbounded quantifiers removed (giving it three more free variables). The Grand Finale Functions For some satisfaction predicate \(\#\) , that predicate's grand finale function applied to \(n\) is the greatest natural number \(k\) such that there exists \(\phi\) in \(\#\) 's domain with less than \(n\) symbols such that \(\forall j \in \mathbb N. (\#(\phi, j) \iff j = k)\) plus 1 (or 0 if no such \(k\) exists). If \(\#\) is definable in first-order set theory, so will its grand finale function. However, there is no formula in first-order set theory assigning such predicates to grand finale functions in general. As a concrete example, let \(f(n)\) equal (drum roll please): :\(\min(\{m \in \mathbb N : \forall k \in \mathbb N. k < m \impliedby \exists \phi \in \Sigma_{100}. |\phi| < n \land \forall j \in \mathbb N. ((\) :\(\exists a. \forall a^\prime . \exists b. \forall b^\prime . \exists c.\forall c^\prime . \exists d. \forall d^\prime . \exists e. \forall e^\prime . \exists f. \forall f^\prime . \exists g. \forall g^\prime . \exists h. \forall h^\prime . \exists i. \forall i^\prime . \exists l. \forall l^\prime . \exists o. \forall o^\prime . \exists p. \forall p^\prime . \exists q. \forall q^\prime . \exists r. \forall r^\prime . \exists s. \forall s^\prime . \exists t. \forall t^\prime . \exists u. \forall u^\prime . \exists v. \forall v^\prime . \exists w. \forall w^\prime. \exists x. \forall x^\prime . \exists y. \forall y^\prime . \exists z. \forall z^\prime . \exists \alpha. \forall \alpha^\prime . \exists \beta. \forall \beta^\prime . \exists \gamma. \forall \gamma^\prime . \exists \delta. \forall \delta^\prime . \exists \epsilon. \forall \epsilon^\prime . \exists \zeta. \forall \zeta^\prime . \exists \eta. \forall \eta^\prime . \exists \theta. \forall \theta^\prime . \exists \iota. \forall \iota^\prime . \exists \kappa. \forall \kappa^\prime . \exists \lambda. \forall \lambda^\prime . \exists \mu. \forall \mu^\prime . \exists \nu. \forall \nu^\prime . \exists \xi. \forall \xi^\prime . \exists \pi. \forall \pi^\prime . \exists \rho. \forall \rho^\prime . \exists \sigma. \forall \sigma^\prime . \exists \tau. \forall \tau^\prime . \exists \upsilon. \forall \upsilon^\prime . \exists \chi. \forall \chi^\prime . \exists \psi. \forall \psi^\prime . \exists \omega. \forall \omega^\prime . \exists \varepsilon. \forall \varepsilon^\prime . \exists \varkappa. \forall \varkappa^\prime . \exists \varpi. \forall \varpi^\prime . \exists \varrho. \forall \varrho^\prime . \exists \varsigma. \forall \varsigma^\prime . \exists \vartheta. \forall \vartheta^\prime .\) :\(\#_\text{Bounded}(\overline \phi, (a, a^\prime, b, b^\prime, c, c^\prime, d, d^\prime, e, e^\prime, f, f^\prime, g, g^\prime, h, h^\prime, i, i^\prime, l, l^\prime, o, o^\prime, p, p^\prime, q, q^\prime, r, r^\prime, s, s^\prime, t, t^\prime, u, u^\prime, v, v^\prime, w, w^\prime, x, x^\prime, y, y^\prime, z, z^\prime, \alpha, \alpha^\prime, \beta, \beta^\prime, \gamma, \gamma^\prime, \delta, \delta^\prime, \epsilon, \epsilon^\prime, \zeta, \zeta^\prime, \eta, \eta^\prime, \theta, \theta^\prime, \iota, \iota^\prime, \kappa, \kappa^\prime, \lambda, \lambda^\prime, \mu, \mu^\prime, \nu, \nu^\prime, \xi, \xi^\prime, \pi, \pi^\prime, \rho, \rho^\prime, \sigma, \sigma^\prime, \tau, \tau^\prime, \upsilon, \upsilon^\prime, \chi, \chi^\prime,\psi, \psi^\prime, \omega, \omega^\prime, \varepsilon, \varepsilon^\prime, \varkappa, \varkappa^\prime, \varpi, \varpi^\prime, \varrho, \varrho^\prime, \varsigma, \varsigma^\prime, \vartheta, \vartheta^\prime,j)) \iff j = k)\) :\(\})\) As a concrete example of a number, we will call \(f(10^{100})\) the finale number. Growth Rate Although these functions are definable in first-order set theory, they are more convenient to analyze using second-order set theory, which we will do in this section. Suppose some function \(f\) is definable by a binary formula \(\phi\) in first-order set theory. For any \(n\) , we can define \(k = f(n)\) via \(\phi(n, k)\) quite straight forwardly. Assuming we are using von neumann ordinals to represent the natural numbers, this means that \(g(c2^x + |\phi| + 1)\) grows faster than \(f\) for some constant \(c\) , where \(g\) is the grand finale function of the satisfaction predicate over the level of the Lévy hierarchy containing \(\phi\) . Of course, this a very loose lower bound, but already shows how quickly the grand finale functions grow. The only condition we placed on \(f\) is that it was definable by a binary formula for some level of the Lévy hierarchy. (I have not figured out exactly how many, but its clear that moving a couple (constant) number of levels in the Lévy hierarchy allows \(f(x)\) to beaten by \(g(x)\) .) In particular, this means that sense every function definable in first order set theory falls in the Lévy hierarchy, there is a grand finale function such that \(g(c2^x + |\phi| + 1)\) beats \(f\) for any first-order set theory definable function \(f\) . Moreover, finding the \(g\) to beat it can be done mechanically: simply count the number of quantifiers used in \(f\) 's definition, and then write the corresponding grand finale function. This makes the grand finale functions the most powerful Googolism in first-order set theory. Any function definable in first-order set theory is beaten by a naive extension of the grand finale function defined above. Even if a function incorporates a grand finale function into its definition, a grand finale function higher up in the Lévy hierarchy will still beat that function, and no function definable in first-order set theory can incorporate all the grand finale functions into its definition. Generalizations It appears that the grand finale functions could be generalized to first-order and second-order arithmetic, as well as second-order set theory. It most likely generalizes to what ever meta-theories the authors of Little Bigeddon and Sasquatch used. Grand Finale Ordinals We can likewise define ordinals in this fashion. For some satisfaction predicate \(#\) , let \(S\) be defined as the set of ordinals \(\alpha\) such that there exists a \(\phi\) in \(#\) 's domain such that for all ordinals \(\beta\) , we have that \(\#(\phi, \beta) \iff \beta = \alpha\) . The predicate's grand finale ordinal is defined as the supremum of \(S\) . We also define the predicate's little grand finale ordinal (which will be countable) as the least ordinal not in \(S\) . System of fundamental sequences We can define a system of fundamental sequences for the little grand finale ordinals. Let \(#\) be a satisfaction predicate, and \(\alpha\) it's little grand finale ordinal. For any limit ordinal \(\beta \le \alpha\) , the ordinals in its fundamental sequence are those that are less than \(\beta\) but greater than every other ordinal less than \(\beta\) whose formula comes before it in the shortlex order. Here is the proof that this is a fundamental sequence: 1. First we will proof that the supremum of the sequence is \(\beta\) . Assume contrary. Let \(\gamma\) be the first ordinal in the shortlex order that is greater than the supremum plus but less than \(\beta\) (this set is non-empty since all the numbers between the supremum and \(\beta\) are less than \(\alpha\) and therefore have a formula). Every ordinal before \(\gamma\) but less than \(\beta\) is less than \(\gamma\) , and so \(\gamma\) is in the sequence. However, \(\gamma\) is greater than the supremum, a contradiction! 2. Now we will proof that the sequence has order type \(\omega\) . The ordinals of the sequence can be mapped to the first formula in the shortlex order to define them. Due to the way the sequence is defined, this mapping will be an order-preserving embedding. Any infinite set that embeds into an ordered set of type \(\omega\) will itself have order type \(\omega\) . Provability These functions are interesting. ZF can not tell us much about the grand finale functions. However, ZF does prove they are well defined. Additionally, ZF is capable of understanding that the grand finale numbers are much greater than certain other numbers. For example, ZF knows that the finale number (defined above) is greater than the googolplexeth busy beaver number. It does not know how much bigger, just that it is bigger. To study the grand finale functions in generality, one should MK set theory. It's language is capable of allowing the number of quantifiers to be an argument, and it's axioms are capable of proving that this overall function is well defined. It also is able to formalize the idea that these functions "lead up" to Rayo's function. Conclusion When the Googolplex was initially defined, its value was determined by the endurance of the person writing. Dr. Kasner, however, was displeased with this definition: A googolplex is much larger than a googol, but is still finite, as the inventor of the name was quick to point out. It was first suggested that a googolplex should be 1, followed by writing zeros until you got tired. This is a description of what would happen if one actually tried to write a googolplex, but different people get tired at different times and it would never do to have Carnera a better mathematician than Dr Einstein, simply because he had more endurance. Mathematics and the Imagination He averted it by redefining Googolplex to be \(10^{10^100}\) . However, the grand finale functions proof his efforts to be in vain. One can not turn the number of quantifiers in the grand finale function into an argument; each and every quantifier must be included in the definition. This means that Carnera or whatever dexterous person you wish to name can defeat any Googolism by writing a grand finale function that simply includes enough quantifiers to defeat it. Even if the competing Googolist tries to incorporate the resulting grand finale function into their definition in interesting and powerful ways, the result can still be defined by yet a longer grand finale function. He can not claim that their adversary is making a naive extension of their function. The adversary is making a naive extension of their own function, only taking into account the length of the Googolists definition. However, all good things must come to an end. We have had lots of fun all the way, learning powerful maths, making friends, and hopefully learning something about ourselves. We've had highs and, well, higher highs. Although all numbers are smaller than most numbers, the numbers we defined were still pretty awesome. All good things must come to an end, and so it is fitting that Googology have not merely a finale, but a grand finale. However, do not consider this the end, but a new beginning. Please, join us next week for part three, return of the hand crampers. But please, first give our performers a hand. Well known Googologists come unto the stage and take a bow while the audience gives thunderous applaud and throws flowers. Curtains close and credits roll via projector. THE END Category:Blog posts